package cuiyt.algorithm.union.optimization;
/**
 * @author cyt
 * @create 2020-09-05 16:20
 */
public class UnionQuPath extends UnionQuRank {
    private int[] rank;

    public UnionQuPath(int cap) {
        super(cap);
        rank = new int[cap];
        for (int i = 0; i < cap; i++) {
            rank[i] = 1;
        }
    }
    /**
     * 出于 树高度的层面来优化
     *
     * @param v
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        if (parents[v] != v) {
            parents[v] = find(parents[v]);
        }
        return parents[v];
    }
}
